//https://leetcode.cn/problems/maximize-grid-happiness/
class Solution {
public:
    int getMaxGridHappiness(int m, int n, int introvertsCount, int extrovertsCount) {
        swap(n, m);
        auto cal = [&](int val) {
            int last = 0;
            int lastv = 0;
            int sum = 0;
            for (int i = 0; i < n; ++i) {
                if (val % 3 == 1) {
                    if (last == 1)sum -= 30;
                    if (lastv == 1)sum -= 30;
                    if (lastv == 2)sum += 20;
                    sum += 120;
                    lastv = 1;
                }
                else if (val % 3 == 2) {
                    if (last == 1)sum += 20;
                    if (lastv == 1)sum -= 30;
                    if (lastv == 2)sum += 20;
                    sum += 40;
                    lastv = 2;
                }
                last = 1;
                if (val % 3 == 0)last = 0, lastv = 0;
                val /= 3;
            }
            return sum;
            };
        auto calc = [&](int val) {
            int cnt1 = 0;
            int cnt2 = 0;
            for (int i = 0; i < n; ++i) {
                if (val % 3 == 1)cnt1++;
                else if (val % 3 == 2)cnt2++;
                val /= 3;
            }
            return make_pair(cnt1, cnt2);
            };
        auto calcc = [&](int val1, int val2) {
            int sum = cal(val2);
            for (int i = 0; i < n; ++i) {
                int res1 = val1 % 3;
                int res2 = val2 % 3;
                // 4 3 2 1 0
                if (res1 > 0 && res2 > 0) {
                    if (res1 + res2 == 4)sum += 40;
                    else if (res1 + res2 == 3)sum -= 10;
                    else sum -= 60;
                }
                val1 /= 3;
                val2 /= 3;
            }
            return sum;
            };
        int M = (int)pow(3, n);
        int dp[M][6][7][7];
        memset(dp, -1, sizeof(dp));
        function<int(int, int, int, int)>dfs = [&](int status, int ii, int x, int y) {
            if (ii == m) return 0;
            if (dp[status][ii][x][y] != -1)return dp[status][ii][x][y];
            int res = 0;
            for (int i = 0; i < M; ++i) {
                auto p = calc(i);
                if (x >= p.first && y >= p.second)
                    res = max(res, dfs(i, ii + 1, x - p.first, y - p.second) + calcc(status, i));
            }
            return dp[status][ii][x][y] = res;
            };
        int ans = -1;
        for (int i = 0; i < M; ++i) {
            pair<int, int> p = calc(i);
            if (introvertsCount >= p.first && extrovertsCount >= p.second)
                ans = max(ans, dfs(i, 1, introvertsCount - p.first, extrovertsCount - p.second) + cal(i));
            // cout<<ans<<" "<<i<<endl;
        }
        // cout<<"-- "<<cal(16)<<endl;
        return ans;
    }
};
